package com.formula.datastructure.exercise.sort.adv;

import com.formula.datastructure.util.DataUtil;

/**
 * 记得有几个点
 * 一是 sort里面需要去调用一个递归函数
 * 二是 有一个while里面套两个while
 * 三是 要记得保留original low high
 */
public class QuickSort {

    // 不需要申明辅助数组
    public Integer[] sort(Integer[] input) {
        quicksort(input, 0, input.length - 1);
        return input;
    }

    /**
     * 错误:
     * #1
     * #2
     *
     * @param array
     * @param origLow
     * @param origHigh
     */
    private void quicksort(Integer[] array, int origLow, int origHigh) {
        if (origLow < origHigh) {
            int low = origLow;
            int high = origHigh;
            // pivot始终为比较, 现在low空出来
            Integer pivot = array[low];

            while (low < high) {
                // 一定是小于等于, 现在找到第一个比pivot小的high, 放到low上去, high空出来
                while (low < high && pivot <= array[high]) {
                    high--;
                }
                array[low] = array[high];
                //一定是大于等于, 再把比pivot大的放到high上面去
                while (low < high && pivot >= array[low]) {
                    low++;
                }
                array[high] = array[low];
            }

            array[low] = pivot;

            // pivot在中间, 只需要比较左右两边
            quicksort(array, origLow, low - 1);
            quicksort(array, low + 1, origHigh);
        }
    }

    public static void main(String[] args) {
        QuickSort quick = new QuickSort();
        Integer[] array = DataUtil.genUniqueArray(12, 100);
        DataUtil.printIndex(12);
        DataUtil.printArray(array);
        DataUtil.printArray(quick.sort(array));
    }
}
